package jalgebrava.group.permutation;

import jalgebrava.util.F;
import jalgebrava.util.collections.ImmutableIterable;
import jalgebrava.util.collections.ImmutableIterator;

import java.util.LinkedList;

// a permutation of the initial integers
public class Permutation {

	private final int n;
	private final int[] p;
	private int[] inv;

	private static F<Integer, Permutation> identityPermutations = F
			.cached(new F<Integer, Permutation>() {

				@Override
				public Permutation apply(Integer a) {
					Permutation result = new Permutation(a);
					int n = result.n;
					for (int i = 0; i < n; i++) {
						result.p[i] = i;
					}
					return result;
				}

			});

	private Permutation(int n) {
		this.n = n;
		this.p = new int[n];
	}

	private Permutation(int n, int[] p) {
		this.n = n;
		this.p = new int[n];
		
		for (int i=0;i<n;i++) {
			this.p[i] = p[i];
		
		}
	}

	private Permutation(int n, int[] p, int[] inv) {
		this.n = n;
		this.p = new int[n];
		this.inv = new int[n];
		for (int i=0;i<n;i++) {
			this.p[i] = p[i];
			this.inv[i] = inv[i];
		}

	}

	public static Permutation identityPermutation(int n) {
		return identityPermutations.apply(n);
	}

	public Permutation inversePermutation() {
		if (this.inv == null) {
			inv = new int[n];
			for (int i = 0; i < n; i++) {
				inv[p[i]] = i;
			}
		}
		return new Permutation(n, inv, p);
	}

	public Permutation multiplyPermutation(Permutation y) {
		if (this.n != y.n) {
			throw new IllegalArgumentException("Permutations not compatible");
		}
		Permutation result = new Permutation(n);
		for (int i = 0; i < n; i++) {
			result.p[i] = this.p[y.p[i]];
		}
		return result;
	}

	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		for (int i=0;i<n;i++) {
			sb.append(p[i]);
		}
		return sb.toString();
	}
	public static ImmutableIterable<Permutation> allPermutationsOfSize(
			final int n) {
		return new ImmutableIterable<Permutation>() {

			@Override
			public ImmutableIterator<Permutation> iterator() {

				return new ImmutableIterator<Permutation>() {
					private int current[];
					private final int len = n;

					@Override
					public boolean hasNext() {
						if (current == null) {
							return true;
						}
						for (int i = 0; i < len - 1; i++) {
							if (current[i] < current[i + 1]) {
								return true;
							}
						}
						return false;
					}

					@Override
					public Permutation next() {
						if (current == null) {
							current = new int[len];
							for (int i=0;i<len;i++) {
								current[i]=i;
							}
							return new Permutation(n, current);
						}
						
						// Find largest index j with a[j] < a[j+1]

						int j = current.length - 2;
						while (current[j] > current[j + 1]) {
							j--;
						}

						// Find index k such that a[k] is smallest integer
						// greater than a[j] to the right of a[j]

						int k = current.length - 1;
						while (current[j] > current[k]) {
							k--;
						}

						// Interchange a[j] and a[k]

						int temp = current[k];
						current[k] = current[j];
						current[j] = temp;

						// Put tail end of permutation after jth position in increasing order

						int r = current.length - 1;
						int s = j + 1;

						while (r > s) {
							temp = current[s];
							current[s] = current[r];
							current[r] = temp;
							r--;
							s++;
						}

						return new Permutation(n, current);
					}

				};
			}

		};
	}

	@Override
	public boolean equals(Object obj) {
		if (obj == null || !(obj instanceof Permutation)) {
			return false;			
		}
		Permutation obj2 = (Permutation) obj;
		if (this.n != obj2.n) {
			return false;
		}
		for (int i=0;i<n;i++) {
			if (this.p[i] != obj2.p[i]) {
				return false;
			}
		}
		return true;
	}

	@Override
	public int hashCode() {
		// interpret p as base n
		int result = 0;
		for (int i=0;i<n;i++) {
			result *= n;
			result += p[i];
		}

		return result;
	}

	public int getSizeOfSetActedUpon() {
		return n;
	}

	public static Permutation mk(int size, int[] images) {
		boolean[] seen = new boolean[size];
		for (int im: images) {
			if (im < 0 || im >= size) {
				throw new RuntimeException("Illegal Permutation");
			}
			if (!seen[im]) {
				seen[im] = true;
			}
		}
		// here: no double images, same size, so must be okay.
		return new Permutation(size, images);
	}

	// cycle notation: (a b c) ( d e  )
	// empty is (), NOT empty string
	public static Permutation mk(int size, String string) {

		int[] images = new int[size];
		for (int i=0;i<size; i++) {
			images[i] = i;
		}
		
		for (String piece: string.split("\\)")) {
			LinkedList<Integer> nums = new LinkedList<Integer>();
			for (String numString: piece.split("\\(| ")) {
				if (numString.trim().length() == 0) {
					continue;
				}
				nums.add(Integer.parseInt(numString));				
			}
			if (nums.size() <= 1) {
				continue;
			}
			int first = nums.get(0);
			for (int i=0;i<nums.size()-1;i++) {
				if (images[nums.get(i)] != nums.get(i)) {
					throw new RuntimeException("Cycle decomposition moves element more than once");
				}
				images[nums.get(i)] = nums.get(i+1);
			}
			if (images[nums.get(nums.size()-1)] != nums.get(nums.size()-1)) {
				throw new RuntimeException("Cycle decomposition moves element more than once");
			}
			images[nums.get(nums.size()-1)] = first;
			
		}
		return new Permutation(size, images);
	}
	
}
